package com.zhugang.week02;


/**
 * @program algorithms
 * @description: LinkedList
 * @author: chanzhugang
 * @create: 2022/05/28 9:00
 */
public class MyLinkedList {

    /**
     * 自定义链表
     */
    public class Node {
        public int data;
        public Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node() {

        }
    }

    /**
     * head指针，指向头节点
     */
    private Node head = null;

    /**
     * 遍历
     */
    public void traverse(Node head) {
        Node p = head;
        while (p != null) {
            System.out.println(p.data);
            // p指针后移一位
            p = p.next;
        }
    }

    /**
     * 查找
     *
     * @return
     */
    public Node find(int val) {
        Node p = head;
        while (p != null) {
            if (p.data == val) return p;
            p = p.next;
        }
        return null;
    }

    /**
     * 插入
     * 1、在链表头部插入
     * 2、在链表尾部插入元素
     * 3、在给定结点之后插入元素
     */


    /**
     * 链头插入
     *
     * @param val
     */
    public void insertAtHead(int val) {
        Node newNode = new Node(val, null);
        newNode.next = head;
        head = newNode;
    }

    /**
     * 链尾插入 O(n)：遍历找到尾节点；插入
     *
     * @param val
     */
    public void insertAtTail(int val) {
        Node newNode = new Node(val, null);
        if (head == null) {
            // 链表为null
            head = newNode;
        } else {
            Node p = head;
            while (p.next != null) {
                p = p.next;
            }
            // 此时p为尾节点
            p.next = newNode;
        }
    }

    /**
     * 记录链表尾结点的位置
     */
    private Node tail;

    /**
     * 优化一：添加tail指针,降低时间复杂度： O(1)
     *
     * @param val
     */
    public void insertAtTail2(int val) {
        Node newNode = new Node(val, null);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    /**
     * 优化二：引入虚拟头结点（哨兵结点）: 借助虚拟结点 + 以及tail指针，简化链尾插入(特殊处理去掉了)
     * 虚拟头节点不存储数据
     *
     * @param val
     */
    private final Node virtualNode = new Node();
    private Node tail3 = virtualNode;

    public void insertAtTail3(int val) {
        Node newNode = new Node(val, null);
        tail3.next = newNode;
        tail3 = newNode;
    }

    /**
     * 在给定结点之后插入
     *
     * @param p
     * @param val
     */
    public void insertAtAfter(Node p, int val) {
        // new.next = p.next; p.next = new
        if (p == null) {
            return;
        }
        Node newNode = new Node(val, null);
        newNode.next = p.next;
        p.next = newNode;
    }

    /**
     * 删除：
     * 1、删除给定结点之后的结点
     */
    public void deleteNextNode(Node p) {
        if (p == null || p.next == null) {
            return;
        }
        // 删除p之后的节点：java里会把p.next回收
        p.next = p.next.next;
    }

    /**
     * 特殊处理：头节点
     * 删除给定结点: 找到删除结点的前置结点（遍历，记录prev）
     *
     * @param head
     * @param p
     */
    public Node deleteThisNode(Node head, Node p) {
        // 找到p节点的前置节点prev， prev.next = prev.next.next
        if (head == null || p == null) {
            return null;
        }
        Node q = head;
        Node prev = null;
        while (q != null) {
            if (q == p) {
                break;
            }
            prev = q;
            q = q.next;
        }
        if (q == null) {
            // 链表中没有p节点
            return head;
        }
        if (prev == null) {
            // 此时p是头节点，头节点往后挪一位
            head = head.next;
        } else {
            prev.next = prev.next.next;
        }
        return head;
    }

    /**
     * 删除给定节点：引入虚拟头节点
     *
     * @param head
     * @param p
     * @return
     */
    public Node deleteThisNode2(Node head, Node p) {
        // 引入虚拟头节点，简化编程（不用判断边界条件）
        // 遍历找到p节点的前置节点, prev.next = prev.next.next
        if (head == null || p == null) {
            return null;
        }
        Node newHead = new Node();
        newHead.next = head;
        // prev 指向虚拟头节点
        Node prev = newHead;
        Node q = head;
        while (q != null) {
            if (q == p) {
                break;
            }
            prev = q;
            q = q.next;
        }
        if (q == null) {
            return head;
        }
        prev.next = prev.next.next;
        return newHead.next;
    }
}